Sensitive information is usually encrypted when it has to be sent through an insecure channel, so that only the intended receiver can decrypt it. Therefore, other people, entities or systems accessing this information are unable to understand it.
Methods already known from the state of the art are used to ensure the integrity of the encrypted message during the transmission, such as digital signatures. However, the receiver must generally trust that the decryption process recovers the plaintext message that corresponds to the received cipher text. The decryption application is usually trusted, in the sense that it does not change the result of the decryption process. However, when this operation is done by a third party, this could manipulate the information recovered after decryption. Currently, this problem has been approached in message decryption processes where the anonymity of the message source has to be preserved. Since this kind of processes does not only decrypt the information, but also performs other operations in order to anonymize it, several methods have been proposed for providing verification tools that validate the correct behavior of both the anonymization and the decryption processes.
Preserving Anonymity in Decryption Processes
There are schemes in which the decryption process must preserve the anonymity of the entities which have encrypted the information. An electronic voting system is an example of such schemes. In electronic voting systems, it is very important not to know the relationship between the content of a vote and the identity of the voter who cast it. For this purpose, some decryption processes used in these schemes break the correlation between the encrypted messages (linked to their source) and the decrypted ones (not linked). The most known technique for that is based on Mixnets.
A Mixnet is a permutation network composed by one or more servers or nodes which perform message permutation and decryption processes. The purpose of the Mixnet is to obtain decrypted information at the output which is not correlated with the encrypted information from the input. To achieve that, a first node receives input messages from different sources, which have been previously encrypted, and applies a transformation function to them, which generally is composed by a permutation and an encryption or decryption operation (depending on the type of Mixnet). In case the Mixnet is composed by more than one node, the transformed messages are sent to the next node. The same operations of permutation and encryption or decryption are repeated at each node sequentially, until the last node processes the messages. The original values of the messages (before they were encrypted) are obtained at the output of the last node. The purpose of Mixnets is to create an anonymous communication channel in order to preserve the privacy of the participants in a communication.
The origin of Mixnets goes back to the concept created by David Chaum [Ch81], which was originally proposed for anonymous communication by electronic mail. In that proposal, messages are encrypted several times by using nested encryption layers using an RSA cryptosystem with random padding. Each Mixnet node (Mix-node from now) has a public key pki and a private key ski. Messages (m) sent through the Mixnet are prepared at the sources by encrypting them as many times as the number of nodes composing the Mixnet, using the public keys of the nodes in the other way round than the order in which they will process the messages. The result is an onion encryption composed by nested encryption layers, where each layer is decrypted when the encrypted message is processed by the specific node owning the corresponding private key:M=pk1(pk2 . . . (pkn-1(pkn(m,rn),rn-1),rn-2) . . . ,r1)
Therefore, each message m is encrypted several times using different public keys pki and random paddings ri. The first node uses its private key to decrypt the first encryption layer for all the input messages, permutes them and sends them to the next node. This operation is repeated at each node until the plaintexts are recovered in the last node.
Several proposals, called “chaumian Mixnets” or decryption Mixnets have they origin in the proposal described in [Ch81], like [FOO92 and JJR02]. In all them, messages are anonymized by means of a multiple layer encryption at the beginning and a decryption and permutation Mixnet. The main problem of these proposals is that the encryption operations to be done at the origin increases with the number of nodes in the Mixnet. Moreover, since padding is added each time the message is encrypted, the size of the resulting cipher text also increases with the number of nodes.
Looking for a solution to the problems described above, Park et al. [PIK94] proposed the first re-encryption and partial decryption Mixnet. In their proposal, messages sent to the Mixnet are encrypted only once using a cryptosystem with re-encryption properties. A cryptosystem with re-encryption properties is defined as a cryptosystem where, given a public key P, a private key S, and an encrypted message C obtained from the encryption of a message m with P, the re-encryption of a cipher text C is a cipher text C′ that results in the same original message m when it is decrypted with the private key S:C=Pk(m)C′=Pk(C)Sk(C′)=Sk(C)=m 
ElGamal or Paillier are cryptosystems with re-encryption properties.
In this kind of Mixnets, the first node receives the encrypted messages, permutes them, encrypts them again with the same public key P and partially decrypts them with a private key owned by the node. ElGamal or Paillier cryptosystems use random values when encrypting the message in order to get a different value each time a plaintext is encrypted (called probabilistic cryptosystems). When performing the re-encryption operation, a new random value is combined with the value already used to make the previous encryption:mj=Pk(mi,ri+rj)
Permutation, re-encryption and partial decryption operations are performed at each Mix-node. The output of the last node are the decrypted messages.
In all the Mixnet proposals described above (chaumian or re-encryption ones) the main purpose is to anonymize the sources of the messages. However, they have a common problem: they are not robust in front of an attack over the integrity of the encrypted messages. In case one of the nodes decides to change the values of the transformed messages, the next node cannot detect it. In fact, an external observer cannot distinguish between the output of a node when it behaves properly than the output when it is malicious and substitutes the values of all or some messages.
Later proposals give more importance to a property called universal verifiability in order to be able to detect a cheating node. Mixnets with this property provide a proof of the correct behavior of the Mixnet, in such a way that any entity can verify this proof (the verifier entity does not need to know any secret or sensitive information, like private keys, to verify the proof). With this proof, the verifier can check that the messages at the output of a Mix-node are the same (but transformed) than the ones received at the input. Sako and Killian [SK95] proposed the first universally verifiable Mixnet based in the re-encryption and partial decryption Mixnet proposed in [PIK94]. In their proposal, each node publishes the result of partially decrypting each input, before re-encrypting and permuting the inputs. Then, all nodes provide a proof of the re-encryption and permutation operations.
The permutation proof is based in the following cryptographic proofs, also known as a zero knowledge proofs because the verifier gets to know anything about the sensitive information needed to generate them when checking their validity:
Assume that πi and ri are the permutation and random values (for re-encryption) used by a node i. The node generates another set of permutation λi and random ti values, and performs an alternative re-encryption and permutation process using this second set, generating a second output. The verifier challenges the node (the prover) to reveal either (λi, ti), which proves that the second transformation was done properly, or the difference between the first and second transformation (λiπi−1, (ri−ti)), which allows to the verifier to check that the output of the original transformation can be obtained by permuting and re-encrypting the outputs of the second transformation. The correct behavior of the Mixnet is then verified with a 50% of probability of being right. The number of alternative transformations and verifications can be increased in order to achieve a higher probability.
In 1998, Abe [Ab98] proposed an extension of the scheme described in [SK95] in order to reduce the amount of work required from the verifier, and to have a number of verifications independent of the number Mix-nodes. In the proposed re-encryption Mixnet, provers (nodes) have to make additional operations in order to provide a joint proof of their actions. The main contribution is the chaining of proofs of different nodes, so that the verifier only has to verify the proof of the last node. Nodes perform a secondary transformation to prove the correctness of the re-encryption and permutation operations, like in [SK95]. The main difference is that the second transformation is based in the second transformation of the previous node, instead of the input messages of the actual node. In case the verifier challenges the second transformation, then all the nodes reveal the values of their second transformations simultaneously. Otherwise, if the verifier challenges the difference between the first and second transformation, the nodes sequentially compute the difference and reveal it in turn. Anyway, the verifier just has to verify one transformation (the secondary, or the difference between the primary and the secondary). The cost of verifying the decryption process is also independent of the number of nodes, since the nodes cooperate to generate the decryption factor, and provide a chained zero knowledge proof to prove that this decryption factor was generated properly.
In 2002, Jakobsson et al. [JJR02] presented a verification technique called RPC (Randomized Partial Checking). This technique can be applied to all Mixnets, independently of the encryption and permutation methods they use. In RPC, each node has to reveal the relationship between an input and an output for half of the processed messages (i.e., the permutation and a proof of encryption/decryption for each revealed link), which are selected in a random way. Therefore, a node could manipulate n messages with a probability of going undetected of 2−n. Regarding source anonymity, the privacy of the input-output relationships among the nodes of the Mixnet is protected with a certain probability of disclosure that is decreased with the number of nodes, which can be enhanced by carefully selecting the input-output relationships to be disclosed at each node: when selecting the relations to audit at random, a complete disclosure of input-output relationship through the Mixnet (in all the Mix-nodes) could be revealed (which means that, for that message, we could know its source), violating the privacy of the message source. This can be solved by grouping the nodes by pairs: node 1 with node 2, node 3 with node 4, and so on. With this node grouping, half of the messages in the first node of each pair is selected at random, and the half of messages to be selected in the second node depends on the non-selected in the first one. The selected messages are verified at each node by pairs. This way, the whole trajectory of a message in the Mixnet is never disclosed, protecting source anonymity. However, this anonymity depends on half of the nodes being honest.
Although the trajectory of a message through the Mixnet is protected from disclosure with this last method, revealing half of the links at each Mixing node provides some extra information to the verifier, who gets to know that the probability of an input message to be in a specific output of the Mixnet may be higher than in the other proposals (the probability from the point of view of the verifier is not equally distributed among all the outputs).
In 2004 Chaum [Ch04] solved this issue by grouping the nodes in groups of 4. At each group, the information of half of randomly selected messages of the first node is revealed, and the information of other half is revealed in the second node. Finally, half of the messages revealed in the second node and another half of the revealed in the third node, are revealed in the third node and the remaining set is revealed in the four. This way, the probability, from the point of view of the verifier, of an input message to be in an specific output is equally distributed among all the outputs.
The probability of detection of a cheating node is still very low for small quantities of manipulated messages. For example, the chances of detecting the manipulation of two messages are about 75%, so there is a 25% of probability that this manipulation goes undetected. This percentage is independent of the total number of messages in the Mixnet.
In the invention EP1633077A2, also described in [Ne01], another universally verifiable Mixnet is proposed. In this invention, the verification of the correctness of the Mixnet operations, which uses the ElGamal cryptosystem, is done by interactive zero knowledge proofs. In this scheme, the verification system is based on the property of polynomial invariance independently of the permutation of their roots. This verification system is better than the RPC proposal in the sense that it fully protects the anonymity of the message source (it is not based on revealing pieces of paths of the messages through the nodes, but on proving mathematical relationships between input and output messages at each node). Moreover, the probability of detection of a manipulated message is higher, being this scheme the most robust of the schemes presented by now. The main drawback of this system is that the computation and verification of the mathematical proofs has a very high computational cost.
After this proposal, Golle et al. [Go02] proposed a new universally verifiable Mixnet called “Optimistic Mixing”, with proofs that are significantly faster than other proposals of verifiable Mixnets, in case all the nodes behave honestly. For each node, the input messages are multiplied together, and so are the output messages. A zero knowledge proof showing that both results contain the same encrypted value is used to detect any misbehavior in the Mixnet. For proving that, the proposal takes profit of the homomorphic properties of certain cryptosystems. In case the proof is not correct, a more robust and slow Mixing verification scheme is used to detect the cheating node/s, for example [Ne01].
This scheme also improves the RPC systems from the point of view of the anonymity of the source, since the disclosure of any permutation or information about the encrypted messages is not needed for the verification process. The probability of detection of manipulated messages can be better or worse than in RPC systems, depending on the specific situation. Since the verification is based on the product of inputs and outputs of each node, a malicious node could manipulate two messages in such a way that the manipulation is canceled when multiplying (for example, by multiplying a message by a value and dividing another message by the same). Therefore, certain message manipulations may not be detected by this scheme.
Some of the verifiable Mixnet schemes previously described achieve a robust verification process by using a high number of cryptographic proofs, which is very costly from the point of view of computation resources. Therefore, it is very difficult to implement these schemes for practical applications where time may be a constraint. Others, like those based on RPC, have a probability of detection very low in case of Mixnets processing a short amount of messages, and they may not maintain a 100% anonymity level of the message sources. On the other side, the most efficient scheme ([Go02]) needs to use slower systems in case of detecting any error.
The present invention is based on the implementation of a source-anonymizing verifiable decryption system solving the efficiency problems of verifiable Mixnets that use zero knowledge proofs to prove their correct behavior, maintaining a high probability of detection of possible manipulations, and that does not depend on the number of nodes to guarantee the anonymity of the message sources.